package leetcode_600;

/**
 *@author 周杨
 *DeleteOperationForTwoStrings_583 给定两个字符串 求删除任一字符串的某个字符为一步 最少多少步能让两个字符串相等 
 *describe:变相用动态规划求两个字符串的最长公共序列  AC 13%
 *2018年9月17日 上午10:50:12
 */
public class DeleteOperationForTwoStrings_583 {
	public int minDistance(String word1, String word2) {
        if(word1.length()==0)
        	return word2.length();
        if(word2.length()==0)
        	return word1.length();
        char c1[]=word1.toCharArray();
        char c2[]=word2.toCharArray();
        int dp[][]=new int[word1.length()+1][word2.length()+1];
        //开始求最长公共序列 
       for(int i=1;i<=word1.length();++i)
    	   for(int j=1;j<=word2.length();++j) {
    		   if(c1[i-1]==c2[j-1]) {
    			   dp[i][j]=dp[i-1][j-1]+1;
    		   }
    		   else {
    			   dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
    		   }
    	   }
        return word1.length()+word2.length()-dp[word1.length()][word2.length()];
    }
}
